﻿#include <iostream>
#include <vector>
#include <stdexcept>

class AdjacencyMatrix {
private:
    std::vector<std::vector<int>> matrix;
    int numVertices;
    bool directed;

public:
    // 构造函数
    AdjacencyMatrix(int n, bool isDirected = false)
        : numVertices(n), directed(isDirected) {
        // 初始化n x n的矩阵，所有元素设为0
        matrix.resize(n, std::vector<int>(n, 0));
    }

    // 添加边
    void addEdge(int i, int j, int weight = 1) {
        if (i < 0 || i >= numVertices || j < 0 || j >= numVertices) {
            throw std::out_of_range("顶点索引越界");
        }

        matrix[i][j] = weight;
        if (!directed) {
            matrix[j][i] = weight; // 如果是无向图，对称位置也设置
        }
    }

    // 移除边
    void removeEdge(int i, int j) {
        if (i < 0 || i >= numVertices || j < 0 || j >= numVertices) {
            throw std::out_of_range("顶点索引越界");
        }

        matrix[i][j] = 0;
        if (!directed) {
            matrix[j][i] = 0;
        }
    }

    // 检查是否存在边
    bool hasEdge(int i, int j) const {
        if (i < 0 || i >= numVertices || j < 0 || j >= numVertices) {
            throw std::out_of_range("顶点索引越界");
        }

        return matrix[i][j] != 0;
    }

    // 获取边的权重
    int getEdgeWeight(int i, int j) const {
        if (i < 0 || i >= numVertices || j < 0 || j >= numVertices) {
            throw std::out_of_range("顶点索引越界");
        }

        return matrix[i][j];
    }

    // 获取顶点数量
    int getNumVertices() const {
        return numVertices;
    }

    // 打印邻接矩阵
    void print() const {
        std::cout << "邻接矩阵:\n";
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                std::cout << matrix[i][j] << " ";
            }
            std::cout << "\n";
        }
    }

    // 获取顶点的邻居
    std::vector<int> getNeighbors(int v) const {
        if (v < 0 || v >= numVertices) {
            throw std::out_of_range("顶点索引越界");
        }

        std::vector<int> neighbors;
        for (int i = 0; i < numVertices; i++) {
            if (matrix[v][i] != 0) {
                neighbors.push_back(i);
            }
        }
        return neighbors;
    }
};
/*
优势 ✅
查询速度快：O(1)时间判断边是否存在

实现简单：数据结构直观易懂

适合稠密图：当边数接近V²时效率高

支持矩阵运算：便于数学分析和算法实现

局限性 ❌
空间效率低：O(V²)空间复杂度，不适合大规模稀疏图

添加/删除顶点困难：需要重新调整矩阵大小

遍历邻居效率低：需要扫描整行，O(V)时间

总结
邻接矩阵最适合以下场景：

图规模较小（顶点数不超过几百个）

图比较稠密（边数接近顶点数的平方）

需要频繁查询边是否存在

需要利用矩阵运算进行图分析

权重图算法实现（如Floyd-Warshall）

在选择图表示方法时，应根据具体应用场
*/
int main() {
    // 创建一个有5个顶点的无向图
    AdjacencyMatrix graph(5, false);

    // 添加边
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    // 打印邻接矩阵
    graph.print();

    // 检查特定边是否存在
    std::cout << "\n边(0,1)存在: " << (graph.hasEdge(0, 1) ? "是" : "否") << std::endl;
    std::cout << "边(0,2)存在: " << (graph.hasEdge(0, 2) ? "是" : "否") << std::endl;

    // 获取顶点1的所有邻居
    std::vector<int> neighbors = graph.getNeighbors(1);
    std::cout << "顶点1的邻居: ";
    for (int n : neighbors) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    // 移除一条边并重新打印
    graph.removeEdge(1, 4);
    std::cout << "\n移除边(1,4)后的邻接矩阵:\n";
    graph.print();

    return 0;
}